class Solution
{
public:
    string clearStars(string s)
    {
        vector<set<int>> charPos(26);
        vector<int> starPos;
        int n = s.size();
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '*')
            {
                starPos.push_back(i);
            }
            else
            {
                charPos[s[i] - 'a'].insert(i);
            }
        }

        for (int star : starPos)
        {
            for (char c = 'a'; c <= 'z'; ++c)
            {
                auto pos = charPos[c - 'a'].lower_bound(star);
                if (pos != charPos[c - 'a'].begin())
                {
                    --pos;
                    int i = *pos;
                    s[i] = '.';
                    charPos[c - 'a'].erase(i);
                    break;
                }
            }
        }
        string result;
        for (char c : s)
        {
            if (c != '.' && c != '*')
            {
                result.push_back(c);
            }
        }
        return result;
    }
};